This invention relates to a technique for generating test patterns for logic circuits and, more particularly, to a method and apparatus for compressing test patterns which detect faults in logic circuits.
Increases in the scale of large-scale integration generally is accompanied by use of a method wherein a test pattern generating process which generates test patterns for detecting faults in logic circuits such as logical LSI devices is provided with a pattern compression processing step for reducing the pattern length of the test patterns, without lowering the fault detection rate of the test patterns, before the generated test patterns are supplied to the LSI tester. According to this method, it is the test patterns compressed by the pattern compression step that are supplied to the LSI tester. The reason for adopting this method is that higher integration and functionality of LSI devices is associated with test patterns of larger scale, making it necessary to compress the test patterns in advance in order to raise testing efficiency so as to overcome limitations on test-pattern memory (local memory) with which the LSI tester is equipped.
Conventionally, test pattern compression is carried out by assigning an undefined value (also referred to as an xe2x80x9cindeterminate valuexe2x80x9d) X (Don""t Care), which will not lower fault detection performance, to the fault-detection test patterns and trying pattern merging in accordance with prescribed rules on a plurality of test patterns to which the undefined value X has been assigned. A known method of assigning the undefined value X to fault detection test patterns is to assign the undefined value X to input pins that do not participate in fault detection, e.g., input pins that do not possess paths to an output pin at which a fault has been detected.
A test pattern comprises rows and columns, and the number of a row starting from the first row is referred to as the xe2x80x9cpattern numberxe2x80x9d. The columns correspond to the pins of the logic circuit. The pattern of the first row is applied simultaneously to the input pins of the device (logic circuit) undergoing testing in the LSI tester. This pattern is referred to also as a xe2x80x9ctest vectorxe2x80x9d. The pattern applied to the input pins of the device being tested is treated as a test pattern.
A fault model of a logic circuit and assignment of the undefined value X to test patterns will be described below. The fault dealt with in a logic-circuit fault simulation is a modeled logical fault. The model usually used is a simple degenerate fault model. The simple degenerate fault model has such a fault that the output of a gate circuit, for example, is always fixed at 0 (a 0 degeneracy fault, or xe2x80x9cstuck at 0xe2x80x9d) or at 1 (a 1 degeneracy fault, or xe2x80x9cstuck at 1xe2x80x9d) regardless of the input to the gate circuit.
Faults in a logic circuit will be discussed in general taking as an example a combinational circuit illustrated in FIG. 10A. This combinational circuit. is such that when the output of an OR gate OR2 has developed a 1 degeneracy fault (stuck at 1) Sa1, the output of this OR gate is always xe2x80x9c1xe2x80x9d and never xe2x80x9c0xe2x80x9d even when the input side thereof is supplied with a pattern that should make the output xe2x80x9c0xe2x80x9d. Accordingly, with regard to a pattern for detecting the fact that the output of the OR gate OR2 is stuck at 1, it is necessary to detect that the OR gate OR2 outputs xe2x80x9c1xe2x80x9d when xe2x80x9c0xe2x80x9d is applied to both inputs of the OR gate OR2. To achieve this, it is required to make (0, 0) the two inputs to the OR gate OR2 and to make xe2x80x9c1xe2x80x9d the output of an OR gate OR3 whose output is connected to one input terminal of an AND gate AND6 the other input terminal of which has the output of OR gate OR2 connected thereto. It will suffice to make (0, 0) the two inputs to an OR gate OR1, which will output xe2x80x9c0xe2x80x9d, and to make xe2x80x9c0xe2x80x9d one of the two inputs to the AND gate AND3. For this it will suffice to make xe2x80x9c0xe2x80x9d one of the two inputs of each of AND gates AND1, AND2 whose output terminals are connected to the input side of the OR gate OR1. Further, it will suffice to make xe2x80x9c1xe2x80x9d one of the two inputs to the OR gate OR3. If the output of an AND gate AND4 has been made xe2x80x9c1xe2x80x9d, then it will suffice to make xe2x80x9c1xe2x80x9d both inputs to the AND gate AND4 and to make xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d the output of an AND gate AND5.
In order to compress test patterns for detecting faults in a logic circuit, the undefined value X is assigned to input pins for which it does not matter whether the assigned values are xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d. In a case where an undefined value X in a test pattern is input to an LSI tester, the value is set to xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d.
In order to detect the Sa1 fault at the output of the OR gate OR2, the test pattern applied to input pins I1-I10 of the logic circuit is made xe2x80x9c0100101101xe2x80x9d, as shown in FIG. 10A. However, since the input pins I2, I3, I9 and I10 play no part in fault detection, undefined values X are assigned to these pins. As a result, the generated test pattern will be xe2x80x9c0XX0X011XXxe2x80x9d. The test pattern with the assigned undefined values X is merged with other test patterns in the row direction in accordance with a predetermined rule, whereby compression is achieved. Processing for achieving pattern merging will be described in detail later.
Another method of compressing a test pattern known in the art is to switch the order of test patterns.
The configuration and operation of a system used in compressing test patterns according to the related art will now be described.
FIG. 8 illustrates a system configuration according to a related art. In an information processor (referred to as a xe2x80x9clocal CPUxe2x80x9d) 10A which executes pattern compression processing, circuit information 301 concerning a logic circuit to be tested is read into the system by circuit information read-in means 304, fault information 302 is read into the system by fault information read-in means 305, a test pattern (pattern information) 303 is read into the system by pattern information read-in means 306 and a repeated random-number fault simulation is run for all faults. The test pattern 303 to be compressed is created automatically by ATPG (Automatic Test Pattern Generation), semi-automatically or manually. If the information composed of the circuit information 301, fault information 302 and pattern information 303 has been stored in a file unit, then the read-in means 304, 305, 306 constitute input means for inputting the information from the file unit. On the other hand, if the information composed of the circuit information 301, fault information 302 and pattern information 303 resides in a server or the like (not shown) connected to a network, then the read-in means 304, 305, 306 constitute communication means for downloading the circuit information 301, fault information 302 and pattern information 303 from the server.
The fault information 302 comprises a list of paired information, namely faults and fault insertion points (node information) in logic circuit. As mentioned earlier, the fault dealt with in the fault simulation is the logical fault Sa0 (stuck at 0) or Sa1 (stuck at 1).
A random-number fault simulation assigns xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d to undefined values in a test pattern-using random numbers, thereby activating the undefined values to carry out the fault simulation.
More specifically, in order to perform pattern compression by pattern merging, undefined values X are inserted into the test pattern, which has been read into the system by the pattern-information read-in means 306, at locations that are not necessary for fault detection, as described earlier.
By assigning xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d to the undefined values X in this test pattern, the undefined values are activated to remove them from within the logic circuit undergoing inspection. Using pseudo-random numbers generated based upon random-number-sequence initial-value information 308 set by random-number-sequence initial-value setting means 307, means 309 for generating random numbers and assigning them to undefined values assigns a sequence of xe2x80x9c0xe2x80x9ds or xe2x80x9c1xe2x80x9ds, in which the probability of occurrence thereof is random, to the undefined values X in succession, thereby generating test patterns 310 in which the undefined values X have been activated. By thus activating the undefined values X using random numbers, the possibility of fault detection is increased.
Using the test patterns 310 in which the undefined values have been activated using pseudo-random numbers and the circuit information and fault information that has been read in, fault simulation means 311 executes fault simulation.
The fault simulation means 311 sets a fault, which has been stipulated in the fault information 302, at a node of the logic circuit, applies the test patterns as an input and subjects the logic circuit to a logical simulation by a logic simulator to obtain an output pattern. Then, without inserting the fault, the simulation means applies the test patterns as the input and subjects the logic circuit to a logical simulation by the logic simulator to obtain the output pattern. It is assumed that a fault has been detected when the two output patterns do not match.
On the basis of the result of fault detection output from the fault simulation means 311, test patterns in which the undefined values have been activated are checked for fault detection capability on a per-pattern-number basis and patterns of pattern numbers that do not detect the fault are discarded. In addition, even pattern numbers of patterns that detect the fault have undefined values X assigned by undefined-value assigning means 312 to pins that do not participate in the fault detection, whereby test patterns (pattern information) 313 are created.
Test patterns output from the undefined-value assigning means 312 are merged by pattern merging means 315. If predetermined conditions are satisfied, pattern output means 316 outputs the merged test patterns as output pattern information 317.
Fault-detection-status list output means 318 outputs information 319, which represents the status of output fault detection, from fault-detection status information 314 to a file or output unit.
FIG. 9 is a flowchart useful in describing pattern compression processing in a system of the related art, and FIG. 11 is a schematic view useful in describing pattern compression using a repeated random-number fault simulation. Pattern compression processing in the system of the related art will be described with reference to FIGS. 9 and 11.
Circuit information, fault information and test patterns are read in (steps S21-S23).
Test patterns for detecting a list of faults f1-f8 [see (a) of FIG. 11] that have been defined for the particular logic circuit are created, a pattern (referred to as xe2x80x9cPattern 1xe2x80x9d) of Pattern No. 1 detects faults f1, f2, f3, a pattern (referred to as xe2x80x9cPattern 2xe2x80x9d) of Pattern No. 2 detects faults f4, f5, f6, and a pattern (referred to as xe2x80x9cPattern 3xe2x80x9d) of Pattern No. 3 detects faults f7 and f8 [see (b) of FIG. 11].
Next, after initial values of the random-number sequence are set, xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d is assigned to the undefined values X using pseudo-random numbers (steps S24 and S25 in FIG. 9). One method of assignment is to assign xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d depending upon whether the value of a function which generates pseudo-random numbers having numerical values between 0.0 and 1.0 is less than 0.5 or equal to or greater than 0.5. Setting initial values of a random-number sequence involves setting initial values used in the computation of the pseudo-random numbers in the function for generating the pseudo-random numbers. The function (implemented by the processor of the local CPU) for generating the pseudo-random numbers generates a random-number sequence (R1, R2, . . . Rm, . . . ) successively by executing an arithmetic operation based upon a prescribed recursion formula Rn+1=ƒ(Rn) in which a given initial value serves as the first random number R0 (referred to as a xe2x80x9cseed random numberxe2x80x9d).
By way of example, the undefined values X in columns 9, 10, 13, 14 of Pattern 1 among the Patterns 1-3 in (b) of FIG. 11 become the object of activation by assignment of xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d based upon the first to fourth random numbers (R1-R4) of the pseudo-random number sequence; the undefined values X in columns 4, 6, 10, 13, 14 of Pattern 2 become the object of activation by assignment of xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d based upon the fifth to ninth random numbers (R5-R9), and the undefined values X in columns 3, 4, 6, 8, 10, 12, 14 of Pattern 3 become the object of activation by assignment of xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d based upon the tenth to sixteenth random numbers (R10-R16) As a result, Patterns 1-3 of the kind shown in (c) of FIG. 11, for example, are obtained as test patterns to which xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d has been assigned (i. e., test patterns whose undefined values have been activated) based upon the above-mentioned sequence of pseudo-random numbers.
With reference again to FIG. 9, fault simulation is carried out (step S26) using the test patterns whose undefined values X have been activated by xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d.
As a result of the fault simulation in the example shown at (d) of FIG. 11, faults f1-f4, f5, f8 are detected using Pattern 1, faults f5, f6, f7 are detected using Pattern 2 and no faults can be detected using Pattern 3.
As a result, Pattern 3 which does not detect any faults is discarded, as shown at (e) of FIG. 11, whereby compression to the two pattern lengths of Patterns 1 and 2 is achieved, and undefined values are assigned to pins not related to fault detection in each of the two remaining patterns.
Discarding Pattern 3 is equivalent to saying that none of the pins of Pattern 3 participate in fault detection. Undefined values X are assigned to all pins of Pattern 3, and the pattern having the undefined values X assigned to all pins is merged with any other pattern by the pattern merging means 315. Essentially, therefore, this corresponds to eliminating the pattern. In other words, rather than eliminating Pattern 3 at the stage of (e) in FIG. 11, a pattern xe2x80x9cXXXXXXXXXXXXXXXXxe2x80x9d in which the values of all columns of Pattern 3 have been made undefined values X may be generated at step (f) in FIG. 11.
The test patterns created are then merged by the pattern merging means 315 (step S27 in FIG. 9).
Next, it is determined whether the test pattern obtained by pattern merging satisfies a predetermined final condition (step S28 in FIG. 9). If the final condition is not satisfied, processing is repeated from the setting of the initial values of the random-number sequence at step S24 in FIG. 9. If the final condition is satisfied, however, output-pattern information is output from the pattern output means 316 (step 29 in FIG. 9). A case where the fault detection rate has attained a preset target fault detection rate is used as the final condition, by way of example. Alternatively, a case where the pattern compression rate has attained a preset fixed value or a case where the number of repetitions has exceeded a predetermined number may serve as the final condition.
The details of processing executed by the pattern merging means 315 will be described next. In a case where a certain pin (column) of two patterns has the same value in the patterns or at least one of the values is an undefined value X, the two values are said to be xe2x80x9cmergiblexe2x80x9d. In a case where the values of all pins (columns) in the two patterns are mergible, then these two patterns are said to be mergible. Two patterns which do not satisfy this condition are said to be xe2x80x9cnon-mergiblexe2x80x9d.
If a column of the two patterns has identical values, this value appears in the corresponding column of the pattern resulting from merging, and if a column of the two patterns has one undefined value, the value other than the undefined value appears in the corresponding column of the pattern resulting from merging.
Pattern merging will be described in detail using the example shown in FIG. 12. As shown in FIG. 12, the pattern of Pattern 1 is xe2x80x9cX10XX0X1xe2x80x9d and the pattern of Pattern 2 is xe2x80x9cXX01X001xe2x80x9d. In Patterns 1 and 2, the columns corresponding to input pins a and e have undefined values X for both patterns; the columns corresponding to input pins c and h have xe2x80x9c0xe2x80x9ds and xe2x80x9c1xe2x80x9ds, respectively, for both patterns; and the columns corresponding to input pins b, d, f and g have an undefined value X for one pattern and either xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d for the other pattern. Since all pins a-h are thus mergible, the two patterns are merged into a single pattern. The pattern obtained by such merging is a compressed pattern xe2x80x9cX101X001xe2x80x9d.
The pattern merging means 315 tries pattern merging for combinations of all pattern numbers among the test patterns.
Though not illustrated in FIG. 8, the order of test patterns may be reversed. This is to perform a fault simulation by rearranging the pattern numbers in reverse order. Test patterns are compressed by specifying patterns that are not necessary for fault detection and discarding these patterns. For a description of a reversing fault simulation method, refer to xe2x80x9cSOCRATES: A Highly Efficient Automatic Test Pattern Generation Systemxe2x80x9d, IEEE. Trans. On CAD., pp. 126-137, January 1988). Thus, in a case which includes a step of reversing the order of the test patterns, assignment of xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d to undefined values of a test pattern using random numbers, fault simulation, assignment of undefined values to a test pattern, pattern merging and reversal of the pattern order are repeated until the prescribed final condition is satisfied in accordance with the processing procedure described above.
It should be noted that means for assigning undefined values to test patterns and means for pattern merging are described in the specification of Japanese Patent Application Laid-Open JP-A-8-212799, by way of example.
The methods of the related art described above are disadvantageous in that pattern compression requires an extended period of time for processing. The reason for this is that the series of processes for achieving pattern compression by assigning xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d as undefined values in test patterns using random numbers, performing fault simulation, assigning undefined values to test patterns and merging patterns is executed in a single information processor.
Fault simulation involves comparing the results of simulation applied to a normal logic circuit and the results of simulation applied to a logic circuit into which faults have been introduced. A consequence of this approach is that an increase in the scale of logic circuits to be inspected and in the number of faults defined for logic circuits is accompanied by an increase in the processing time needed for fault analysis. In other words, when a series of processes for pattern compression is executed by a single information processor, an enormous amount of computation is required for a large-scale integrated circuit and this leads to longer processing time.
Further, there is a preceding Japanese Patent Application No. 11-139144 (undisclosed at the time of filing of the present application) assigned to NEC IC Microcomputer Systems, Ltd., a subsidiary of the assignee of the present invention describes a method which includes the steps of assigning either the state xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d to test patterns; discarding test patterns which cannot detect faults in a logic circuit from among test patterns in which xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d has been assigned to undefined values and changing locations in a test pattern that are unnecessary for detecting faults to undefined values; merging test patterns among the undiscarded remaining test patterns that are capable of being merged in accordance with a predetermined rule; and changing the order of a plurality of test patterns contained in a set of test patterns The entire disclosure of the Japanese Patent Application No. 11-139144 is herein incorporated by reference thereto. However, there is still much desired also for the method of this preceding application.
Accordingly, an object of the present invention is to provide a method, system and apparatus, as well as a program product and a medium carrying the applicable programs, for speeding up pattern compression by repeated random-number fault simulation and for improving compression efficiency.
According to a first aspect of the present invention, there is provided a test pattern compression method of executing the following steps in distributed fashion by a plurality of processing units:
(a) a repeated random-number fault simulation step which includes:
(a1) creating test patterns in which undefined values in test patterns that inspect a logic circuit for faults defined for the logic circuit have been activated by assigning xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d to these undefined values based upon a random-number sequence;
(a2) running a fault simulation on the logic circuit using fault information and the test patterns in which the undefined values have been activated; and,
(a3)generating and outputting, on the basis of results of the fault simulation, test patterns having undefined values assigned to values for pins that do not participate in fault detection in the test patterns in which the undefined values have been activated; and
(b) pattern merging the test patterns generated and output by the repeated random-number fault simulation step (a);
wherein (c) the faults defined for the logic circuit are divided into a plurality of fault groups (in conformity with the number of the plurality of processing units), the fault groups are assigned to respective ones of the plurality of processing units, and (d) the plurality of processing units execute the repeated random-number-fault simulation step for the logic circuit independently of one another using the fault groups that have been assigned to respective ones of the processing units.
In a second aspect of the present invention, the initial values of the random numbers are used in common by the plurality of processing units that run the random-number fault simulation step, whereby test patterns before compression by the repeated random-number fault simulations performed by the plurality of processing units are made the same. This holds down an increase in test pattern length.
In a third aspect of the present invention, when test patterns generated as a result of running the repeated random-number fault simulation step by the plurality of processing units are subjected to pattern merging, pattern length is maintained the same as that of the test patterns before compression by merging those test patterns, which have been generated by different processing units, that have identical pattern numbers, after which test patterns having different pattern numbers are subjected to pattern merging, thereby reducing length of the test patterns.
According to a fourth aspect of the present invention, there is provided a test pattern compression apparatus. The apparatus comprises: one processing unit and 1st to Nth (where N is a positive integer equal to or greater than 2) processing units connected to the one processing unit, configured for compressing and outputting test patterns, wherein the one processing unit has fault dividing means for dividing faults defined for a logic circuit to be inspected into a plurality of fault groups and assigning the fault groups to the 1st to Nth processing units, the one processing unit supplying the fault groups to respective ones of the corresponding 1st to Nth processing units and supplying circuit information relating to the logic circuit, test patterns to undergo compression processing and initial-value information of a random-number sequence to the 1st to Nth processing units.
(a) The 1st to Nth processing units each have:
(a1) means for generating test patterns in which undefined values in the test patterns have been activated by assigning xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d to these undefined values based upon a random-number sequence that has been generated from the initial-value information of the random-number sequence;
(a2) means for inserting the divided faults into the logic circuit and running a fault simulation using the test patterns in which the undefined values have been activated; and
(a3) undefined-value assignment means for checking fault detection performance of the test patterns in which the undefined values have been activated, on the basis of fault-detection result information obtained by the fault simulation, and generating test patterns having undefined values assigned to input pins that do not participate in fault detection of the logic circuit in the test patterns in which the undefined values have been activated.
(b) The one processing unit further has pattern merging means for acquiring pluralities of test patterns that have been generated by the undefined-value assignment means of respective ones of the 1st to Nth processing units, generating first test patterns obtained by merging those test patterns, which have been generated by different processing units, that have identical pattern numbers among the pluralities of test patterns, and then attempting merging among the generated first test patterns, which have different pattern numbers from one another.
According to a fifth aspect of the present invention, there is provided a program product for operating a test pattern compression apparatus, which comprises one processing unit and 1st to Nth (where N is a positive integer equal to or greater than 2) processing units connected to the one processing unit, for compressing and outputting test patterns. The program product has a program for causing the one processing unit to execute the following steps (a) to (c): (a) a dividing step of dividing faults defined for a logic circuit to be inspected into a plurality of fault groups and assigning the fault groups to the 1st to Nth processing units, (b) a step of supplying the divided fault groups to respective ones of the 1st to Nth processing units and for supplying circuit information relating to the logic circuit, test patterns to undergo compression processing and initial-value information relating to generation of a random-number sequence to the 1st to Nth processing units, and (c) a step of acquiring Pluralities of test patterns that have been generated by respective ones of the 1st to Nth processing units, generating first test patterns obtained by merging those test patterns, which have been generated by different processing units, that have identical pattern numbers among said pluralities of test patterns, and then attempting pattern merging among the generated first test patterns, which have different pattern numbers from one another.
And the program product further has a program for causing each of the 1st to Nth processing units to execute the following steps (d) to (f): (d) a step of generating test patterns in which undefined values in the test patterns transmitted from the one processing unit have been activated by generating a pseudo-random-number sequence from the initial-value information relating to the generation of the random-number sequence and assigning xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d to the undefined values, (e) a step of inserting the divided faults into the logic circuit and running a fault simulation using the test patterns in which the undefined values have been activated, and (f) a step of checking fault detection performance of the test patterns in which the undefined values have been activated, on the basis of fault-detection result information obtained by the fault simulation, and generating test patterns having undefined values assigned to values of input pins of said logic circuit that do not participate in fault detection of said logic circuit in the test patterns in which the undefined values have been activated.